package Demo3;

import com.sun.org.apache.xerces.internal.dom.CDATASectionImpl;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2023-04-21
 * Time: 7:09
 */
public class SingleList {
    // 节点类
    public static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head; // 头结点

    public void createNode() {
        // 创建节点
        ListNode listNode1 = new ListNode(11);
        ListNode listNode2 = new ListNode(22);
        ListNode listNode3 = new ListNode(33);
        ListNode listNode4 = new ListNode(44);
        ListNode listNode5 = new ListNode(55);

        // 修改指向
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        // listNode5.next = null;

        // 指定头结点
        head = listNode1;
    }

    public void disPlayNode() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    // 统计节点个数
    public int size() {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    // 判断是否存在某一个指定节点
    public boolean contains(int key) {
        if (head == null) {
            throw new RuntimeException("当前链表为空!");
        }
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    // 头插法
    public void headAdd(int data) {
        ListNode node = new ListNode(data);
        // 当前链表没有节点
        if (head == null) {
            head = node;
            return;
        }
        // 当前链表节点不为0, 修改指向
        node.next = head;
        head = node;
    }

    // 尾插法
    public void tailAdd(int data) {
        ListNode node = new ListNode(data);
        ListNode cur = head;
        if (head == null) {
            head = node;
            return;
        }
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }

    // 将指定位置插入节点 -- index 从 0 下标开始
    public void indexAdd(int index, int data) {
        // 判断index 是否合法
        if (index < 0 || index > size()) {
            throw new RuntimeException("index 插入位置不合法!");
        }

        ListNode node = new ListNode(data);
        // 寻找index位置
        if (index == 0) {
            // 头插法
            headAdd(data);
        } else if (index == size()) {
            tailAdd(data);
        } else {
            // 寻找index 位置
            ListNode cur = head;
            while (index - 1 != 0) {
                cur = cur.next;
                index--;
            }
            // 判断 cur.next 来判断是否已经遍历结束
            if (cur == null) {
                throw new RuntimeException("index 位置插入不合法!");
            }
            // 修改指向
            node.next = cur.next;
            cur.next = node;
        }
    }

    // 删除值为 key 的指定节点
    public void deleteKey(int key) {
        if (head == null) {
            throw new RuntimeException("当前链表为空, 无法删除!");
        }

        ListNode cur = head.next; // cur 相当于从第二个节点开始
        ListNode prev = head; // prev 相当于记录 cur 前一个节点位置
        while (cur != null) {
            if (cur.val == key) {
                break;
            }
            cur = cur.next;
            prev = prev.next;
        }

        if (head.val == key) {
            // 链表只有一个节点且正好为要删除的节点
            head = null;
            return;
        }
        // 修改指向
        prev.next = cur.next;

    }

    // 删除所有值为 key 的节点
    public void deleteAllKey(int key) {
        int count = 0; // 统计是否进行删除操作
        if (head == null) {
            throw new RuntimeException("当前链表为空, 无法删除!");
        }

        ListNode cur = head.next;
        ListNode prev = head;

        while (cur != null) {
            if (cur.val == key) {
                // 更改指向
                prev.next = cur.next;
                count++;
            } else {
                prev = cur;
            }
            cur = cur.next;
        }

        // 单独判断头结点
        if (head.val == key) {
            head = head.next;
            count++;
        }
        if (count == 0) {
            throw new RuntimeException("当前链表无要删除指定节点!");
        }
    }

    // 清空链表
    public void clear() {
        head = null;
    }

    // 按照指定链表头结点打印
    public void headDisPlay(ListNode newHead) {
        if (newHead == null) {
            throw new RuntimeException("当前链表为空!");
        }
        ListNode cur = newHead;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    // 翻转节点 -- 头插法即为逆序输出
    public ListNode reserve() {
        // 没有节点可以翻转
        if (head == null) {
            return null;
        }
        // 只有一个节点无需翻转, 返回当前头结点
        if (head.next == null) {
            return head;
        }
        // 至少有两个及以上节点
        ListNode cur = head.next;
        // 将头结点 next 置空
        head.next = null;
        while (cur != null) {
            // 记录翻转前位置防止后续节点丢失
            ListNode curNext = cur.next;
            // 先绑定后面
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    // 寻找中间节点比如 一共六个节点则第三、四个节点为中间节点, 输出第四个节点
    //               一共五个节点, 则第三个为中间节点, 输出第三个节点
    public ListNode midNode() {
        // 快慢双指针
        // fast 指针从第一个节点开始, 一次走两个节点
        // slow 指针从第一个节点开始, 一次走一个节点
        ListNode fast = head;
        ListNode slow = head;
        if (head == null) {
            throw new RuntimeException("链表为空, 无法查询!");
        }
        // fast != null 判定偶数个节点时
        // fast.next != null 判定奇数个节点时
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }


    // 寻找倒数第 K 个节点
    public ListNode indexNode(int index) {
        if (head == null) {
            throw new RuntimeException("当前链表为空, 无法查询!");
        }

        if (index <= 0) {
            throw new RuntimeException("当前链表为此位置节点!");
        }
        ListNode fast = head;
        ListNode slow = head;

        // 由于fast 从第一个节点开始向后走, 第一步不算, 因此 fast 指针先走 index - 1 步
        while (index - 1 != 0) {
            fast = fast.next;
            if (fast == null) {
                // 一共五个节点, 倒数第六个则要走 5 步, 此时 fast 已经为空
                throw new RuntimeException("index 位置不合法, 请重新输入!");
            }
            index--;
        }

        // fast 领先 index - 1 步
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 判断是否为回文结构 1  2  2  1 为回文   1  2  2  1  1 非回文  1  2  3  2  1 回文
     *
     * @param head 给定的链表头结点
     * @return 判断是否为回文
     */
    public boolean isPalindrome(ListNode head) {
        // 链表为空
        if (head == null) {
            return false;
        }
        // 只有一个节点, 一定为回文
        if (head.next == null) {
            return true;
        }
        // 1. 寻找中间节点 - 快慢指针
        ListNode fast = head;
        ListNode slow = head;
        // fast != null 为奇数时    fast.next != null 为偶数时
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 此时 slow 一定指向中间节点, 但是 fast 不一定在尾节点, 偶数时在尾节点前一个节点
        // 2. 翻转中间节点之后的所有节点
        ListNode cur = slow.next; // 记录当前要反转的节点
        while (cur != null) {
            ListNode curNext = cur.next; // 记录即将下一个需要反转的位置避免丢失
            cur.next = slow; // 修改指向, 即翻转当前节点
            slow = cur; // 修改 slow 让节点翻转结束时, slow 也到达了尾节点
            cur.next = curNext; // 指向下一个要翻转的节点
        }
        // 此时, slow 一定指向翻转之后的尾结点
        while (head != slow) {
            if (head.val != slow.val) {
                return false;
            }
            // 偶数时情况特殊, 比如 1 2 2 1
            // 因为是从中间节点之后的节点开始翻转, 因此第一个翻转的节点指向中间节点
            if (head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        // 为奇数情况下, 全部走完了
        return true;
    }

    //以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

    /**
     * 链表分割
     *
     * @param head 给定链表头结点
     * @param x    给定要根据分割的值
     * @return 返回分割后的链表新头结点
     */
    public ListNode partition(ListNode head, int x) {
        // 将节点划分为 X 满足条件左右两侧的节点
        // 左侧 < X  右侧 >= X
        // 每一侧都定义两个头结点例如 be-指向头 bs指向该侧所有节点的尾
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = head;
        if (head == null) {
            return null;
        }
        while (cur != null) {
            if (cur.val < x) {
                // 首次添加节点
                if (bs == null) {
                    bs = cur;
                    be = cur;
                } else {
                    // 非第一次加入节点, 只需要 be 往后更改指向就行一直保持 be在该部分的尾结点
                    be.next = cur;
                    be = be.next;
                }
            } else {
                if (as == null) {
                    as = cur;
                    ae = cur;
                } else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }

        // 如果节点都大于等于 x , 则左侧没有节点
        if (bs == null) {
            return as;
        }
        // 说明此时一定有左侧节点
        be.next = as;
        // 此时有左侧节点, 如果有右侧节点, 则修改指向链接左右两侧节点
        if (as != null) {
            ae.next = null;
        }
        // 如果节点都小于 x , 没有右侧节点
        return bs;
    }

    public boolean isPalindrome1(ListNode head) {
        // 1. 寻找中间节点
        // 快慢指针
        if (head == null) {
            return false;
        }
        // 只有一个节点
        if (head.next == null) {
            return true;
        }
        // 至少有两个节点
        ListNode fast = head;
        ListNode slow = head;
        // 条件分别为偶数 奇数情况下
        while (fast != null && fast.next != null) {
            fast = fast.next.next; // 一次两步
            slow = slow.next; // 一次一步
        }

        // 此时 slow 指向中间节点
        // 2. 翻转链表, 将中间节点以后的节点都翻转
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode curNext = cur.next; // 记录后面一个节点防止丢失
            cur.next = slow; // 要反转的第一个节点指向前一个节点
            slow = cur; // slow向后移动
            cur = curNext; // 向后移动记录下一个要反转的节点
        }

        // 结束后, 此时slow 和 fast 都指向当前最后一个节点, 且中节点之后的已经翻转
        // 3. 判断回文
        // 用 slow 来判断是由于偶数情况下, fast指向最后一个节点的前一个
        while (head != slow) {
            if (head.val != slow.val) {
                return false;
            }
            // 偶数情况下 1 2 2 1
            if (head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

    /**
     * 相交链表 - 找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null
     *
     * @param headA 给定单链表的头节点
     * @param headB 给定单链表的头结点
     * @return 返回相交节点
     * 双指针思想, 当快指针走长度差步以后, 快慢指针一起走, 如果相遇则为相交节点, 否则没有相交
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0;
        int lenB = 0;
        ListNode curA = headA;
        ListNode curB = headB;
        if (headA == null) {
            return null;
        }
        if (headB == null) {
            return null;
        }

        while (curA != null) {
            lenA++;
            curA = curA.next;
        }
        while (curB != null) {
            lenB++;
            curB = curB.next;
        }

        curA = headA;
        curB = headB;
        int len = lenA - lenB;
        if (len < 0) {
            // 让 lenA 永远指向最长的那个链表
            curA = headB;
            curB = headA;
            len = lenB - lenA; // 修正 len 长度差
        }
        while (len-- != 0) {
            curA = curA.next;
        }
        while (curA != curB) {
            curA = curA.next;
            curB = curB.next;

        }

        if (curA == null) {
            return null;
        }
        return curA;
    }

    /**
     * 环形连边 - 给定一个链表, 判断链表是否有环
     *
     * @param head 链表的头结点
     * @return 是否有环
     * 双指针追及问题:
     * 如果快指针一次三步, 慢指针一次一步, 如果圈里的节点比较小即环小, 那么需要很多圈才能相遇
     * 如果快指针一次三步, 慢指针一次一步, 有可能出现环中有两个节点, 但是永远没法相遇
     * 如果快指针一次两步, 慢指针一次一步, 那么尽可能小的圈内循环次数中相遇, 提高性能
     */
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        if (head == null) {
            return false;
        }
        // 奇数偶数情况下, 快指针走完了没有相遇则为遍历结束
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 判断是否相遇
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    /**
     * 环形链表II - 给定一个链表的头节点  head ，返回链表开始入环的第一个节点
     *
     * @param head 给定的头结点
     * @return 返回入口点
     * 双指针:
     * 判断是否有环, 有环后,此时 fast 和 slow 在相遇点
     * 设相遇点到入口点为 Y 环为 C , 初始点到入口点 为X
     * 则有 X = (N - 1) C + Y
     * 当 N = 1时, X = Y 说明起始点到入口点的距离等于相遇点到入口点距离
     *
     * 那么为什么选 N 为 1 时 ?
     * 由于这里是 fast 走一步, slow 走两步, 因此是最少循环 环圈数内相遇, 因此 N 为 1;
     */
    public ListNode detectCycle(ListNode head) {
        // 1. 判断是否有环, 有环才有入口点
        ListNode fast = head;
        ListNode slow = head;
        if (head == null) {
            return null;
        }
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                // 有环
                break;
            }
        }
        // 其中一个被破坏掉, 都说明无环
        if (fast == null || fast.next == null) {
            return null;
        }
        // 此时有环
        slow = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
